<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>

        function strStr(s1, s2) {
            function getNext(arr, m) {
                let next = []
                next[0] = -1
                if (m === 1) return next
                next[1] = 0
                let i = 2
                let cn = 0
                while (i < m) {
                    if (arr[i - 1] === arr[cn]) {
                        next[i++] = ++cn
                    } else if (cn === 0) {
                        next[i++] = 0
                    } else {
                        cn = next[cn]
                    }
                }
                return next
            }
            let n = s1.length
            let m = s2.length
            let next = getNext(s2, m)
            let i = 0
            let j = 0
            while (i < n && j < m) {
                if (s1[i] === s2[j]) {
                    i++
                    j++
                } else if (j === 0) {
                    i++
                } else {
                    j = next[j]
                }
            }
            return j === m ? i - j : -1
        }
        // console.log(getNext('aabaaf',6))
        console.log(strStr('aabaacaabaabaabaaf', 'aabaaf'))
    </script>
</body>

</html>